import java.util.Stack;

/**
 * Created by loso on 2017/3/26.
 */
public class _155_MinStack {



}

class MinStack {

    int minValue;
    int minCount;

    Stack<Integer> stack;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        minValue = Integer.MAX_VALUE;
        minCount = 0;
    }

    public void push(int x) {
        stack.push(x);
        if (x== minValue){
            minCount++;
        }else if (x < minValue){
            minValue = x;
            minCount = 1;
        }
    }

    private void checkMin(){
        Stack<Integer> tsatck = new Stack<>();
        minValue = Integer.MAX_VALUE;
        minCount = 0;
        while(!stack.isEmpty()){
            tsatck.push(stack.pop());
        }
        while(!tsatck.isEmpty()){
            push(tsatck.pop());
        }
    }

    public void pop() {
        int t = stack.pop();
        if (t==minValue){
            minCount--;
            if (minCount == 0){
                checkMin();
            }
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minValue;
    }
}


class MinStackBigBoss {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
        // only push the old minimum value when the current
        // minimum value changes after pushing the new value x
        if(x <= min){
            stack.push(min);
            min=x;
        }
        stack.push(x);
    }

    public void pop() {
        // if pop operation could result in the changing of the current minimum value,
        // pop twice and change the current minimum value to the last minimum value.
        if(stack.pop() == min) min=stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}